home *** CD-ROM | disk | FTP | other *** search
/ Over 1,000 Windows 95 Programs / Over 1000 Windows 95 Programs (Microforum) (Disc 1).iso / 0957 / gnugrep / cl / kwset.c < prev    next >
C/C++ Source or Header  |  1996-06-28  |  22KB  |  746 lines
  1. /* kwset.c - search for any of a set of keywords.
  2.    Copyright 1989 Free Software Foundation
  3.           Written August 1989 by Mike Haertel.
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 1, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19.    The author may be reached (Email) at the address mike@ai.mit.edu,
  20.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  21.  
  22. /* The algorithm implemented by these routines bears a startling resemblence
  23.    to one discovered by Beate Commentz-Walter, although it is not identical.
  24.    See "A String Matching Algorithm Fast on the Average," Technical Report,
  25.    IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900
  26.    Heidelberg, Germany.  See also Aho, A.V., and M. Corasick, "Efficient
  27.    String Matching:  An Aid to Bibliographic Search," CACM June 1975,
  28.    Vol. 18, No. 6, which describes the failure function used below. */
  29.  
  30. #pragma warning(disable : 4018) //signed/unsigned mismatch
  31.  
  32. #include <limits.h>
  33. #include <stdlib.h>
  34. #include <stddef.h>
  35. #include <sys/types.h>
  36. #include <string.h>
  37. #include <memory.h>
  38.  
  39. extern char *xmalloc();
  40. #define malloc xmalloc
  41.  
  42. #include "kwset.h"
  43. #include "obstack.h"
  44.  
  45. #define NCHAR (UCHAR_MAX + 1)
  46. #define obstack_chunk_alloc malloc
  47. #define obstack_chunk_free free
  48.  
  49. /* Balanced tree of edges and labels leaving a given trie node. */
  50. struct tree
  51. {
  52.   struct tree *llink;        /* Left link; MUST be first field. */
  53.   struct tree *rlink;        /* Right link (to larger labels). */
  54.   struct trie *trie;        /* Trie node pointed to by this edge. */
  55.   unsigned char label;        /* Label on this edge. */
  56.   char balance;            /* Difference in depths of subtrees. */
  57. };
  58.  
  59. /* Node of a trie representing a set of reversed keywords. */
  60. struct trie
  61. {
  62.   unsigned int accepting;    /* Word index of accepted word, or zero. */
  63.   struct tree *links;        /* Tree of edges leaving this node. */
  64.   struct trie *parent;        /* Parent of this node. */
  65.   struct trie *next;        /* List of all trie nodes in level order. */
  66.   struct trie *fail;        /* Aho-Corasick failure function. */
  67.   int depth;            /* Depth of this node from the root. */
  68.   int shift;            /* Shift function for search failures. */
  69.   int maxshift;            /* Max shift of self and descendents. */
  70. };
  71.  
  72. /* Structure returned opaquely to the caller, containing everything. */
  73. struct kwset
  74. {
  75.   struct obstack obstack;    /* Obstack for node allocation. */
  76.   int words;            /* Number of words in the trie. */
  77.   struct trie *trie;        /* The trie itself. */
  78.   int mind;            /* Minimum depth of an accepting node. */
  79.   int maxd;            /* Maximum depth of any node. */
  80.   unsigned char delta[NCHAR];    /* Delta table for rapid search. */
  81.   struct trie *next[NCHAR];    /* Table of children of the root. */
  82.   char *target;            /* Target string if there's only one. */
  83.   int mind2;            /* Used in Boyer-Moore search for one string. */
  84.   char *trans;            /* Character translation table. */
  85. };
  86.  
  87. /* Allocate and initialize a keyword set object, returning an opaque
  88.    pointer to it.  Return NULL if memory is not available. */
  89. kwset_t kwsalloc(char *trans)
  90. //---------------------------
  91. {
  92.   struct kwset *kwset;
  93.  
  94.   kwset = (struct kwset *) malloc(sizeof (struct kwset));
  95.   if (!kwset)
  96.     return 0;
  97.  
  98.   obstack_init(&kwset->obstack);
  99.   kwset->words = 0;
  100.   kwset->trie
  101.     = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));
  102.   if (!kwset->trie)
  103.     {
  104.       kwsfree((kwset_t) kwset);
  105.       return 0;
  106.     }
  107.   kwset->trie->accepting = 0;
  108.   kwset->trie->links = 0;
  109.   kwset->trie->parent = 0;
  110.   kwset->trie->next = 0;
  111.   kwset->trie->fail = 0;
  112.   kwset->trie->depth = 0;
  113.   kwset->trie->shift = 0;
  114.   kwset->mind = INT_MAX;
  115.   kwset->maxd = -1;
  116.   kwset->target = 0;
  117.   kwset->trans = trans;
  118.  
  119.   return (kwset_t) kwset;
  120. }
  121.  
  122. /* Add the given string to the contents of the keyword set.  Return NULL
  123.    for success, an error message otherwise. */
  124. char *kwsincr(kwset_t kws, char *text, size_t len)
  125. //------------------------------------------------
  126. { struct kwset *kwset;
  127.   register struct trie *trie;
  128.   register unsigned char label;
  129.   register struct tree *link;
  130.   register int depth;
  131.   struct tree *links[12];
  132.   enum { L, R } dirs[12];
  133.   struct tree *t, *r, *l, *rl, *lr;
  134.  
  135.   kwset = (struct kwset *) kws;
  136.   trie = kwset->trie;
  137.   text += len;
  138.  
  139.   /* Descend the trie (built of reversed keywords) character-by-character,
  140.      installing new nodes when necessary. */
  141.   while (len--)
  142.     {
  143.       label = kwset->trans ? kwset->trans[(unsigned char) *--text] : *--text;
  144.  
  145.       /* Descend the tree of outgoing links for this trie node,
  146.      looking for the current character and keeping track
  147.      of the path followed. */
  148.       link = trie->links;
  149.       links[0] = (struct tree *) &trie->links;
  150.       dirs[0] = L;
  151.       depth = 1;
  152.  
  153.       while (link && label != link->label)
  154.     {
  155.       links[depth] = link;
  156.       if (label < link->label)
  157.         dirs[depth++] = L, link = link->llink;
  158.       else
  159.         dirs[depth++] = R, link = link->rlink;
  160.     }
  161.  
  162.       /* The current character doesn't have an outgoing link at
  163.      this trie node, so build a new trie node and install
  164.      a link in the current trie node's tree. */
  165.       if (!link)
  166.     {
  167.       link = (struct tree *) obstack_alloc(&kwset->obstack,
  168.                            sizeof (struct tree));
  169.       if (!link)
  170.         return "memory exhausted";
  171.       link->llink = 0;
  172.       link->rlink = 0;
  173.       link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
  174.                              sizeof (struct trie));
  175.       if (!link->trie)
  176.         return "memory exhausted";
  177.       link->trie->accepting = 0;
  178.       link->trie->links = 0;
  179.       link->trie->parent = trie;
  180.       link->trie->next = 0;
  181.       link->trie->fail = 0;
  182.       link->trie->depth = trie->depth + 1;
  183.       link->trie->shift = 0;
  184.       link->label = label;
  185.       link->balance = 0;
  186.  
  187.       /* Install the new tree node in its parent. */
  188.       if (dirs[--depth] == L)
  189.         links[depth]->llink = link;
  190.       else
  191.         links[depth]->rlink = link;
  192.  
  193.       /* Back up the tree fixing the balance flags. */
  194.       while (depth && !links[depth]->balance)
  195.         {
  196.           if (dirs[depth] == L)
  197.         --links[depth]->balance;
  198.           else
  199.         ++links[depth]->balance;
  200.           --depth;
  201.         }
  202.  
  203.       /* Rebalance the tree by pointer rotations if necessary. */
  204.       if (depth && ((dirs[depth] == L && --links[depth]->balance)
  205.             || (dirs[depth] == R && ++links[depth]->balance)))
  206.         {
  207.           switch (links[depth]->balance)
  208.         {
  209.         case (char) -2:
  210.           switch (dirs[depth + 1])
  211.             {
  212.             case L:
  213.               r = links[depth], t = r->llink, rl = t->rlink;
  214.               t->rlink = r, r->llink = rl;
  215.               t->balance = r->balance = 0;
  216.               break;
  217.             case R:
  218.               r = links[depth], l = r->llink, t = l->rlink;
  219.               rl = t->rlink, lr = t->llink;
  220.               t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
  221.               l->balance = t->balance != 1 ? 0 : -1;
  222.               r->balance = t->balance != (char) -1 ? 0 : 1;
  223.               t->balance = 0;
  224.               break;
  225.             }
  226.           break;
  227.         case 2:
  228.           switch (dirs[depth + 1])
  229.             {
  230.             case R:
  231.               l = links[depth], t = l->rlink, lr = t->llink;
  232.               t->llink = l, l->rlink = lr;
  233.               t->balance = l->balance = 0;
  234.               break;
  235.             case L:
  236.               l = links[depth], r = l->rlink, t = r->llink;
  237.               lr = t->llink, rl = t->rlink;
  238.               t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
  239.               l->balance = t->balance != 1 ? 0 : -1;
  240.               r->balance = t->balance != (char) -1 ? 0 : 1;
  241.               t->balance = 0;
  242.               break;
  243.             }
  244.           break;
  245.         }
  246.  
  247.           if (dirs[depth - 1] == L)
  248.         links[depth - 1]->llink = t;
  249.           else
  250.         links[depth - 1]->rlink = t;
  251.         }
  252.     }
  253.  
  254.       trie = link->trie;
  255.     }
  256.  
  257.   /* Mark the node we finally reached as accepting, encoding the
  258.      index number of this word in the keyword set so far. */
  259.   if (!trie->accepting)
  260.     trie->accepting = 1 + 2 * kwset->words;
  261.   ++kwset->words;
  262.  
  263.   /* Keep track of the longest and shortest string of the keyword set. */
  264.   if (trie->depth < kwset->mind)
  265.     kwset->mind = trie->depth;
  266.   if (trie->depth > kwset->maxd)
  267.     kwset->maxd = trie->depth;
  268.  
  269.   return 0;
  270. }
  271.  
  272. /* Enqueue the trie nodes referenced from the given tree in the
  273.    given queue. */
  274. static void enqueue(struct tree *tree, struct trie **last)
  275. //--------------------------------------------------------
  276. {
  277.   if (!tree)
  278.     return;
  279.   enqueue(tree->llink, last);
  280.   enqueue(tree->rlink, last);
  281.   (*last) = (*last)->next = tree->trie;
  282. }
  283.  
  284. /* Compute the Aho-Corasick failure function for the trie nodes referenced
  285.    from the given tree, given the failure function for their parent as
  286.    well as a last resort failure node. */
  287. static void treefails(register struct tree *tree, struct trie *fail, struct trie *recourse)
  288. //-----------------------------------------------------------------------------------------
  289. { register struct tree *link;
  290.  
  291.   if (!tree)
  292.     return;
  293.  
  294.   treefails(tree->llink, fail, recourse);
  295.   treefails(tree->rlink, fail, recourse);
  296.  
  297.   /* Find, in the chain of fails going back to the root, the first
  298.      node that has a descendent on the current label. */
  299.   while (fail)
  300.     {
  301.       link = fail->links;
  302.       while (link && tree->label != link->label)
  303.     if (tree->label < link->label)
  304.       link = link->llink;
  305.     else
  306.       link = link->rlink;
  307.       if (link)
  308.     {
  309.       tree->trie->fail = link->trie;
  310.       return;
  311.     }
  312.       fail = fail->fail;
  313.     }
  314.  
  315.   tree->trie->fail = recourse;
  316. }
  317.  
  318. /* Set delta entries for the links of the given tree such that
  319.    the preexisting delta value is larger than the current depth. */
  320. static void treedelta(register struct tree *tree, register unsigned int depth, 
  321.                                             unsigned char delta[])
  322. //----------------------------------------------------------------------------
  323. { if (!tree)
  324.     return;
  325.   treedelta(tree->llink, depth, delta);
  326.   treedelta(tree->rlink, depth, delta);
  327.   if (depth < delta[tree->label])
  328.     delta[tree->label] = depth;
  329. }
  330.  
  331. /* Return true if A has every label in B. */
  332. static int hasevery(register struct tree *a, register struct tree *b)
  333. //-------------------------------------------------------------------
  334. { if (!b)
  335.     return 1;
  336.   if (!hasevery(a, b->llink))
  337.     return 0;
  338.   if (!hasevery(a, b->rlink))
  339.     return 0;
  340.   while (a && b->label != a->label)
  341.     if (b->label < a->label)
  342.       a = a->llink;
  343.     else
  344.       a = a->rlink;
  345.   return !!a;
  346. }
  347.  
  348. /* Compute a vector, indexed by character code, of the trie nodes
  349.    referenced from the given tree. */
  350. static void treenext(struct tree *tree, struct trie *next[])
  351. //----------------------------------------------------------     
  352. { if (!tree)
  353.     return;
  354.   treenext(tree->llink, next);
  355.   treenext(tree->rlink, next);
  356.   next[tree->label] = tree->trie;
  357. }
  358.  
  359. /* Compute the shift for each trie node, as well as the delta
  360.    table and next cache for the given keyword set. */
  361. char *kwsprep(kwset_t kws)
  362. //------------------------
  363. { register struct kwset *kwset;
  364.   register int i;
  365.   register struct trie *curr, *fail;
  366.   register char *trans;
  367.   unsigned char delta[NCHAR];
  368.   struct trie *last, *next[NCHAR];
  369.  
  370.   kwset = (struct kwset *) kws;
  371.  
  372.   /* Initial values for the delta table; will be changed later.  The
  373.      delta entry for a given character is the smallest depth of any
  374.      node at which an outgoing edge is labeled by that character. */
  375.   if (kwset->mind < 256)
  376.     for (i = 0; i < NCHAR; ++i)
  377.       delta[i] = kwset->mind;
  378.   else
  379.     for (i = 0; i < NCHAR; ++i)
  380.       delta[i] = 255;
  381.  
  382.   /* Check if we can use the simple boyer-moore algorithm, instead
  383.      of the hairy commentz-walter algorithm. */
  384.   if (kwset->words == 1 && kwset->trans == 0)
  385.     {
  386.       /* Looking for just one string.  Extract it from the trie. */
  387.       kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
  388.       for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
  389.     {
  390.       kwset->target[i] = curr->links->label;
  391.       curr = curr->links->trie;
  392.     }
  393.       /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
  394.       for (i = 0; i < kwset->mind; ++i)
  395.     delta[(unsigned char) kwset->target[i]] = kwset->mind - (i + 1);
  396.       kwset->mind2 = kwset->mind;
  397.       /* Find the minimal delta2 shift that we might make after
  398.      a backwards match has failed. */
  399.       for (i = 0; i < kwset->mind - 1; ++i)
  400.     if (kwset->target[i] == kwset->target[kwset->mind - 1])
  401.       kwset->mind2 = kwset->mind - (i + 1);
  402.     }
  403.   else
  404.     {
  405.       /* Traverse the nodes of the trie in level order, simultaneously
  406.      computing the delta table, failure function, and shift function. */
  407.       for (curr = last = kwset->trie; curr; curr = curr->next)
  408.     {
  409.       /* Enqueue the immediate descendents in the level order queue. */
  410.       enqueue(curr->links, &last);
  411.  
  412.       curr->shift = kwset->mind;
  413.       curr->maxshift = kwset->mind;
  414.  
  415.       /* Update the delta table for the descendents of this node. */
  416.       treedelta(curr->links, curr->depth, delta);
  417.  
  418.       /* Compute the failure function for the decendents of this node. */
  419.       treefails(curr->links, curr->fail, kwset->trie);
  420.  
  421.       /* Update the shifts at each node in the current node's chain
  422.          of fails back to the root. */
  423.       for (fail = curr->fail; fail; fail = fail->fail)
  424.         {
  425.           /* If the current node has some outgoing edge that the fail
  426.          doesn't, then the shift at the fail should be no larger
  427.          than the difference of their depths. */
  428.           if (!hasevery(fail->links, curr->links))
  429.         if (curr->depth - fail->depth < fail->shift)
  430.           fail->shift = curr->depth - fail->depth;
  431.  
  432.           /* If the current node is accepting then the shift at the
  433.          fail and its descendents should be no larger than the
  434.          difference of their depths. */
  435.           if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
  436.         fail->maxshift = curr->depth - fail->depth;
  437.         }
  438.     }
  439.  
  440.       /* Traverse the trie in level order again, fixing up all nodes whose
  441.      shift exceeds their inherited maxshift. */
  442.       for (curr = kwset->trie->next; curr; curr = curr->next)
  443.     {
  444.       if (curr->maxshift > curr->parent->maxshift)
  445.         curr->maxshift = curr->parent->maxshift;
  446.       if (curr->shift > curr->maxshift)
  447.         curr->shift = curr->maxshift;
  448.     }
  449.  
  450.       /* Create a vector, indexed by character code, of the outgoing links
  451.      from the root node. */
  452.       for (i = 0; i < NCHAR; ++i)
  453.     next[i] = 0;
  454.       treenext(kwset->trie->links, next);
  455.  
  456.       if ((trans = kwset->trans) != 0)
  457.     for (i = 0; i < NCHAR; ++i)
  458.       kwset->next[i] = next[(unsigned char) trans[i]];
  459.       else
  460.     for (i = 0; i < NCHAR; ++i)
  461.       kwset->next[i] = next[i];
  462.     }
  463.  
  464.   /* Fix things up for any translation table. */
  465.   if ((trans = kwset->trans) != 0)
  466.     for (i = 0; i < NCHAR; ++i)
  467.       kwset->delta[i] = delta[(unsigned char) trans[i]];
  468.   else
  469.     for (i = 0; i < NCHAR; ++i)
  470.       kwset->delta[i] = delta[i];
  471.  
  472.   return 0;
  473. }
  474.  
  475. #define U(C) ((unsigned char) (C))
  476.  
  477. /* Fast boyer-moore search. */
  478. static char *bmexec(kwset_t kws, char *text, size_t size)
  479. //-------------------------------------------------------
  480. { struct kwset *kwset;
  481.   register unsigned char *d1;
  482.   register char *ep, *sp, *tp;
  483.   register int d, gc, i, len, md2;
  484.  
  485.   kwset = (struct kwset *) kws;
  486.   len = kwset->mind;
  487.  
  488.   if (len == 0)
  489.     return text;
  490.   if (len > size)
  491.     return 0;
  492.   if (len == 1)
  493.     return memchr(text, kwset->target[0], size);
  494.  
  495.   d1 = kwset->delta;
  496.   sp = kwset->target + len;
  497.   gc = U(sp[-2]);
  498.   md2 = kwset->mind2;
  499.   tp = text + len;
  500.  
  501.   /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
  502.   if (size > 12 * len)
  503.     /* 11 is not a bug, the initial offset happens only once. */
  504.     for (ep = text + size - 11 * len;;)
  505.       {
  506.     while (tp <= ep)
  507.       {
  508.         d = d1[U(tp[-1])], tp += d;
  509.         d = d1[U(tp[-1])], tp += d;
  510.         if (d == 0)
  511.           goto found;
  512.         d = d1[U(tp[-1])], tp += d;
  513.         d = d1[U(tp[-1])], tp += d;
  514.         d = d1[U(tp[-1])], tp += d;
  515.         if (d == 0)
  516.           goto found;
  517.         d = d1[U(tp[-1])], tp += d;
  518.         d = d1[U(tp[-1])], tp += d;
  519.         d = d1[U(tp[-1])], tp += d;
  520.         if (d == 0)
  521.           goto found;
  522.         d = d1[U(tp[-1])], tp += d;
  523.         d = d1[U(tp[-1])], tp += d;
  524.       }
  525.     break;
  526.       found:
  527.     if (U(tp[-2]) == gc)
  528.       {
  529.         for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
  530.           ;
  531.         if (i > len)
  532.           return tp - len;
  533.       }
  534.     tp += md2;
  535.       }
  536.  
  537.   /* Now we have only a few characters left to search.  We
  538.      carefully avoid ever producing an out-of-bounds pointer. */
  539.   ep = text + size;
  540.   d = d1[U(tp[-1])];
  541.   while (d <= ep - tp)
  542.     {
  543.       d = d1[U((tp += d)[-1])];
  544.       if (d != 0)
  545.     continue;
  546.       if (tp[-2] == gc)
  547.     {
  548.       for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
  549.         ;
  550.       if (i > len)
  551.         return tp - len;
  552.     }
  553.       d = md2;
  554.     }
  555.  
  556.   return 0;
  557. }
  558.  
  559. /* Hairy multiple string search. */
  560. static char *cwexec(kwset_t kws, char *text, size_t len, struct kwsmatch *kwsmatch)
  561. //---------------------------------------------------------------------------------
  562. { struct kwset *kwset;
  563.   struct trie **next, *trie, *accept;
  564.   char *beg, *lim, *mch, *lmch;
  565.   register unsigned char c, *delta;
  566.   register int d;
  567.   register char *end, *qlim;
  568.   register struct tree *tree;
  569.   register char *trans;
  570.  
  571.   /* Initialize register copies and look for easy ways out. */
  572.   kwset = (struct kwset *) kws;
  573.   if (len < kwset->mind)
  574.     return 0;
  575.   next = kwset->next;
  576.   delta = kwset->delta;
  577.   trans = kwset->trans;
  578.   lim = text + len;
  579.   end = text;
  580.   if ((d = kwset->mind) != 0)
  581.     mch = 0;
  582.   else
  583.     {
  584.       mch = text, accept = kwset->trie;
  585.       goto match;
  586.     }
  587.  
  588.   if (len >= 4 * kwset->mind)
  589.     qlim = lim - 4 * kwset->mind;
  590.   else
  591.     qlim = 0;
  592.  
  593.   while (lim - end >= d)
  594.     {
  595.       if (qlim && end <= qlim)
  596.     {
  597.       end += d - 1;
  598.       while ((d = delta[c = *end]) && end < qlim)
  599.         {
  600.           end += d;
  601.           end += delta[(unsigned char) *end];
  602.           end += delta[(unsigned char) *end];
  603.         }
  604.       ++end;
  605.     }
  606.       else
  607.     d = delta[c = (end += d)[-1]];
  608.       if (d)
  609.     continue;
  610.       beg = end - 1;
  611.       trie = next[c];
  612.       if (trie->accepting)
  613.     {
  614.       mch = beg;
  615.       accept = trie;
  616.     }
  617.       d = trie->shift;
  618.       while (beg > text)
  619.     {
  620.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  621.       tree = trie->links;
  622.       while (tree && c != tree->label)
  623.         if (c < tree->label)
  624.           tree = tree->llink;
  625.         else
  626.           tree = tree->rlink;
  627.       if (tree)
  628.         {
  629.           trie = tree->trie;
  630.           if (trie->accepting)
  631.         {
  632.           mch = beg;
  633.           accept = trie;
  634.         }
  635.         }
  636.       else
  637.         break;
  638.       d = trie->shift;
  639.     }
  640.       if (mch)
  641.     goto match;
  642.     }
  643.   return 0;
  644.  
  645.  match:
  646.   /* Given a known match, find the longest possible match anchored
  647.      at or before its starting point.  This is nearly a verbatim
  648.      copy of the preceding main search loops. */
  649.   if (lim - mch > kwset->maxd)
  650.     lim = mch + kwset->maxd;
  651.   lmch = 0;
  652.   d = 1;
  653.   while (lim - end >= d)
  654.     {
  655.       if ((d = delta[c = (end += d)[-1]]) != 0)
  656.     continue;
  657.       beg = end - 1;
  658.       if (!(trie = next[c]))
  659.     {
  660.       d = 1;
  661.       continue;
  662.     }
  663.       if (trie->accepting && beg <= mch)
  664.     {
  665.       lmch = beg;
  666.       accept = trie;
  667.     }
  668.       d = trie->shift;
  669.       while (beg > text)
  670.     {
  671.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  672.       tree = trie->links;
  673.       while (tree && c != tree->label)
  674.         if (c < tree->label)
  675.           tree = tree->llink;
  676.         else
  677.           tree = tree->rlink;
  678.       if (tree)
  679.         {
  680.           trie = tree->trie;
  681.           if (trie->accepting && beg <= mch)
  682.         {
  683.           lmch = beg;
  684.           accept = trie;
  685.         }
  686.         }
  687.       else
  688.         break;
  689.       d = trie->shift;
  690.     }
  691.       if (lmch)
  692.     {
  693.       mch = lmch;
  694.       goto match;
  695.     }
  696.       if (!d)
  697.     d = 1;
  698.     }
  699.  
  700.   if (kwsmatch)
  701.     {
  702.       kwsmatch->index = accept->accepting / 2;
  703.       kwsmatch->beg[0] = mch;
  704.       kwsmatch->size[0] = accept->depth;
  705.     }
  706.   return mch;
  707. }
  708.   
  709. /* Search through the given text for a match of any member of the
  710.    given keyword set.  Return a pointer to the first character of
  711.    the matching substring, or NULL if no match is found.  If FOUNDLEN
  712.    is non-NULL store in the referenced location the length of the
  713.    matching substring.  Similarly, if FOUNDIDX is non-NULL, store
  714.    in the referenced location the index number of the particular
  715.    keyword matched. */
  716. char *kwsexec(kwset_t kws, char *text, size_t size, struct kwsmatch *kwsmatch)
  717. //----------------------------------------------------------------------------
  718. { struct kwset *kwset;
  719.   char *ret;
  720.  
  721.   kwset = (struct kwset *) kws;
  722.   if (kwset->words == 1 && kwset->trans == 0)
  723.     {
  724.       ret = bmexec(kws, text, size);
  725.       if (kwsmatch != 0 && ret != 0)
  726.     {
  727.       kwsmatch->index = 0;
  728.       kwsmatch->beg[0] = ret;
  729.       kwsmatch->size[0] = kwset->mind;
  730.     }
  731.       return ret;
  732.     }
  733.   else
  734.     return cwexec(kws, text, size, kwsmatch);
  735. }
  736.  
  737. /* Free the components of the given keyword set. */
  738. void kwsfree(kwset_t kws)
  739. //-----------------------
  740. { struct kwset *kwset;
  741.  
  742.   kwset = (struct kwset *) kws;
  743.   obstack_free(&kwset->obstack, 0);
  744.   free(kws);
  745. }
  746.